package syf.stack;

import java.util.*;
import java.util.Stack;

public class PolandNotation {
    //先定义给逆波兰表达式
    //（3+4）*5-6  =》 3 4 + 5 * 6 -
    //为了方便数字和符号以空格隔开
    private static final Stack<String> s1=new Stack<>();
    private static final Stack<String> s2=new Stack<>();
    public static void main(String[] args) {
        String  suffixExpression="1 + ( ( 2 + 3 ) * 4 ) - 5";
        ArrayList<String>list=zhongZhuiConvertHouZhui(suffixExpression);//中缀转换成后缀
        int o=calculate(list);//计算
        System.out.println(o);
    }
    //1、将上式放到ArrayList中
    //2、将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
    public static ArrayList<String> getListString(String suffixExpression){
        //分割suffixExpression
        String[] spit=suffixExpression.split(" ");
        return new ArrayList<>(Arrays.asList(spit));
    }

    /**
     * 如果为数就放进去
     * 为符号就弹两个数出来计算
     * @param list 数字和符号
     * @return 计算结果
     */
    public static int calculate(ArrayList<String>list){
        s2.removeAllElements();
        Stack<String> stack=new Stack<>();
        int res=-1;
        for (String x:list){
            //正则表达式取出数
            if (x.matches("\\d+")){
                stack.push(x);
            }
            else {
                int num1=Integer.parseInt(stack.pop());
                int num2=Integer.parseInt(stack.pop());
                switch (x){
                    case("+") :res=num2+num1;break;
                    case("-") :res=num2-num1;break;
                    case("*") :res=num2*num1;break;
                    case("/") :res=num2/num1;break;
                    default:
                        System.out.println("错误的运算符");
                }
                stack.push(res+"");
            }
        }
        return Integer.parseInt(stack.pop());
    }
    public static ArrayList<String> zhongZhuiConvertHouZhui(String suffixExpression){
        String[] spit=suffixExpression.split(" ");
        for (String x:spit){
            if (x.matches("\\d+")){
                s2.push(x);
            }
            else {
                Operation(x);
            }
        }
        s2.push(s1.pop());//已经全部放入到s2中
        return new ArrayList<>(s2);
    }
    public static int priority(int num){
        if ('*'==num|'/'==num)
            return 2;
        else if ('+'==num|'-'==num)
            return 1;
        else
            return 0;
    }
    //判断是否为运算符
    public static boolean isSign(char oper){
        return oper == '*' | oper == '/' | oper == '+' | oper == '-';
    }
    public static void Operation(String x){
        //符号为空或者为左括号直接进s1
        if (s1.empty()||"(".equals(x))
            s1.push(x);
        else if(priority(x.charAt(0))>priority(s1.peek().charAt(0))){//否则当前的优先级比栈顶元素高 入栈
            s1.push(x);
        }
        else if (priority(x.charAt(0))<=priority(s1.peek().charAt(0))&&isSign(x.charAt(0))){
            s2.push(s1.pop());
            //回到开始继续判断
            Operation(x);
        }
        else{//遇到右括号
            if (")".equals(x)) {
                //将左括号右边的都弹入s2
                while (true) {
                    if ("(".equals(s1.peek())){
                        s1.pop();
                        break;
                    }
                    s2.push(s1.pop());
                }
            }
            else {//否则弹出s1顶栈进s2
                s2.push(s1.pop());
            }
        }
    }
}
